1. Field of the Invention
The present invention relates to a Viterbi decoder. More particularly, the present invention relates to calculating a bit error rate (BER) before a Viterbi decoder.
2. Description of the Related Art
Viterbi algorithm is popular for decoding convolution codes in communication systems. For a constraint length of N, there are 2N states in the trellis diagram. A Viterbi decoder has to calculate state metrics for each of the 2N states in order to find out the shortest trellis path. In a conventional Viterbi decoder, an add-compare-select (ACS) unit is used for each state for state metric calculation and trellis path selection.
FIG. 1 is a schematic diagram showing the structure of a conventional ACS unit of a Viterbi decoder. This ACS unit includes two adders 101 and 102, a comparator 103, and a multiplexer (MUX) 104. For example, assume the ACS unit is allocated to state C and there are two candidate source states A and B for the target state C. The adder 101 adds the state metric of state A and the branch metric of the transition from state A to state C, and then provides the result as the first sum. Likewise, the adder 102 adds the state metric of state B and the branch metric of the transition from state B to state C, and then provides the result as the second sum. Here a state metric is an accumulation of a predetermined initial value and the branch metrics of successive state transitions leading to a state. A branch metric is calculated by comparing the target code with the input data received by the Viterbi decoder. The target code is generated from the state transition diagram of the convolution encoder. Each state transition gives a unique output code (Viterbi target code) and implies a unique input data (Viterbi input data).
The comparator 103 compares the first sum and the second sum, and then selects the candidate source state corresponding to the lesser sum as the selected source state of the target state C. One bit of the original data is decoded by this selection of source state out of two candidates. Next, the comparator 103 provides a selection signal SS indicating the selected source state. The metric multiplexer 104 outputs the lesser one of the first sum and the second sum as the state metric of state C according to the selection signal SS.
A Viterbi decoder keeps receiving input data and updating the state metrics of all the states at each reception of an input data symbol until the traceback length is satisfied, and then the Viterbi decoder starts decoding the convolution code by tracing the shortest trellis path. The shortest trellis path begins at the state with the smallest state metric and passes through the chain of sources states of the state with the smallest state metric.
The bit error rate (BER) before Viterbi decoder is a performance criterion for a communication system. FIG. 2 is a schematic diagram showing a conventional circuit for calculating BER before Viterbi decoder. The circuit includes a Viterbi decoder 201, a convolution encoder 202, a storage element 203, and a comparator 204. The Viterbi decoder 201 decodes the Viterbi input data 221. The convolution encoder 202 performs the same convolution encoding as its counterpart in the transmitter of the communication system does on the output of the Viterbi decoder 201. The storage element 203 stores the Viterbi input data 221 and outputs them after some delay so that the output of the convolution encoder 202 can be synchronous with the corresponding Viterbi input data 221. The comparator 204 compares the output of the convolution encoder 202 with the corresponding Viterbi input data 221 provided by the storage element 203 and then outputs the comparison result 222. Each time the comparison result 222 indicates a difference between the output of the convolution encoder 202 and the Viterbi input data 221, the BER is increased by one.
Using this methodology, the Viterbi input data 221 must be saved for a period equal to the traceback length of the Viterbi decoder 201. For example, assume a rate ¼ convolution encoder and a 4-bit soft decision Viterbi decoder are used and the traceback length of the Viterbi decoder is 80, the size of the storage element must be no less than 4*4*80=1280 bits.